#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+10;
int val[N];
int id[N];
int cur;
constexpr double alpha = 0.75;
struct SCT{
    int ls[N];
    int rs[N];
    int siz[N],uc[N];
    bool usf[N];
    int ma[N],cma[N];
    int tot;
    void push_up(int now){
        siz[now] = siz[ls[now]] + siz[rs[now]] + 1;
        uc[now] = uc[ls[now]] + uc[rs[now]] + usf[now];
        ma[now] = max(ma[ls[now]],ma[rs[now]]);
        cma[now] = max(min(ma[ls[now]],ma[rs[now]]),max(cma[ls[now]],cma[rs[now]]));
        if(usf[now]){
            int swp = val[now];
            if(swp > ma[now]){
                swap(swp,ma[now]);
            }
            if(swp > cma[now]){
                swap(swp,cma[now]);
            }
        }
    }
    int build(const vector<int> &rots,int l,int r,int li,int ri){
        if(r < l)return 0;
        int mid = (l + r)/2;
        int imid = (li + ri)/2;
        int now = rots[mid];
        id[now] = imid;
        if(l == r){
            if(usf[now]){
                ma[now] = val[now];
                cma[now] = -1;
            }else{
                ma[now] = cma[now] = -1;
            }
            siz[now] = 1;
            uc[now] = usf[now];
            ls[now] = rs[now] = 0;
            return now;
        }
        ls[now] = build(rots,l,mid - 1,li,imid - 1);
        rs[now] = build(rots,mid + 1,r,imid + 1,ri);
        push_up(now);
        return now;
    }
    void mark_all(int now,vector<int> &rots){
        if(!now)return;
        if(ls[now]){
            mark_all(ls[now],rots);
        }
        rots.push_back(now);
        if(rs[now]){
            mark_all(rs[now],rots);
        }
    }
    bool insert(int &now,int rnk,int p,int dep,int il,int ir){
        int imid = (il + ir)/2;
        if(!now){
            now = p;
            siz[now] = 1;
            uc[now] = usf[now];
            id[now] = imid;
            ls[now] = rs[now] = 0;
            if(usf[now]){
                ma[now] = val[now];
                cma[now] = -1;
            }else{
                ma[now] = cma[now] = -1;
            }
            tot++;
            return dep > log(tot)/log(alpha);
        }
        bool f;
        if(rnk <= uc[ls[now]] + usf[now]){
            f = insert(ls[now],rnk,p,dep + 1,il,imid - 1);
        }else{
            f = insert(rs[now],rnk - uc[ls[now]] - usf[now],p,dep + 1,imid + 1,ir);
        }
        push_up(now);
        if(f && max(siz[ls[now]],siz[rs[now]]) > siz[now]*alpha){
            vector<int> rots;
            mark_all(now,rots);
            now = build(rots,0,rots.size() - 1,il,ir);
            return false;
        }
        return f;
    }
    int rcnt;
    void mark(int now,vector<int> &rots){
        if(!now)return;
        if(ls[now]){
            mark(ls[now],rots);
        }
        if(usf[now]){
            rots.push_back(now);
        }
        if(rs[now]){
            mark(rs[now],rots);
        }
    }
    void remove(int &now,int rnk){
        rcnt++;
        _remove(now,rnk);
        if(rcnt > siz[now]*alpha){
            vector<int> rots;
            mark(now,rots);
            now = build(rots,0,rots.size()-1,1,1e9);
            tot = siz[now];
        }
        return;
    }
    void _remove(int now,int rnk){
        if(usf[now] && uc[ls[now]] + 1 == rnk){
            usf[now] = 0;
        }else if(uc[ls[now]] >= rnk){
            _remove(ls[now],rnk);
        }else{
            _remove(rs[now],rnk - uc[ls[now]] - usf[now]);
        }
        push_up(now);
    }
    int kth(int now,int rnk){
        if(usf[now] && uc[ls[now]] + 1 == rnk){
            return now;
        }else if(rnk <= uc[ls[now]]){
            return kth(ls[now],rnk);
        }else{
            return kth(rs[now],rnk - uc[ls[now]] - usf[now]);
        }
    }
    pair<int,int> merge(pair<int,int> p1,pair<int,int> p2){
        return {max(p1.first,p2.first),max(min(p1.first,p2.first),max(p1.second,p2.second))};
    }
    pair<int,int> qcma(int now,int ix,int iy,int x,int y){
        int imid = (ix + iy)/2;
        if(x <= ix && iy <= y){
            return make_pair(ma[now],cma[now]);   
        }
        pair<int,int> v = {-1,-1};
        if(usf[now] && x <= imid && imid <= y){
            v.first = val[now];
        }
        if(ls[now] && x <= imid - 1){
            pair<int,int> res = qcma(ls[now],ix,imid - 1,x,y);
            v = merge(v,res);
        }
        if(rs[now] && imid + 1 <= y){
            pair<int,int> res = qcma(rs[now],imid + 1,iy,x,y);
            v = merge(v,res);
        }
        return v;
    }
    void deb(int now){
        if(!now){
            return;
        }
        if(ls[now]){
            deb(ls[now]);
        }
        cout<<now<<' '<<val[now]<<' '<<ls[now]<<' '<<rs[now]<<' '<<usf[now]<<' '<<siz[now]<<' '<<uc[now]<<'\n';     
        if(rs[now]){
            deb(rs[now]);
        }
    }
} sct;
struct cmp{
    bool operator()(int a,int b) const{
        return id[a] < id[b];
    }
};
struct Trie{
    set<int,cmp> res[N*22];
    int rot = 1,pcnt = 1;
    int ch[N*22][2];
    void insert(int val,int p)
    {
        int now = rot;
        for(int i = 20;i >= 0;i--){
            int c = (val>>i)&1;
            if(!ch[now][c]){
                ch[now][c] = ++pcnt;
            }
            now = ch[now][c];
            res[now].insert(p);
        }
    }
    int query(int val,int pa,int pb){
        int now = rot;
        int ans = 0;
        for(int i = 20;i >= 0;i--){
            int c = (val>>i)&1;
            if(ch[now][c ^ 1] && res[ch[now][c ^ 1]].lower_bound(pa) != res[ch[now][c ^ 1]].end() && id[*res[ch[now][c ^ 1]].lower_bound(pa)] <= id[pb]){
                ans |= (1<<i);
                now = ch[now][c ^ 1];      
            }else{
                now = ch[now][c];
            }
        }
        return ans;
    }
    void remove(int val,int p){
        int now = rot;
        for(int i = 20;i >= 0;i--){
            int c = (val>>i)&1;
            now = ch[now][c];
            res[now].erase(p);
        }
    }
}trie;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int rot;
    sct.ma[0] = -1;
    sct.cma[0] = -1;
    int n,m;
    cin>>n>>m;
    vector<int> rots;
    for(int i = 1;i<=n;i++){
        cin>>val[i];
        rots.push_back(i);
        sct.usf[i] = 1;
    }
    rot = sct.build(rots,0,n - 1,1,1e9);
    for(int i = 1;i<=n;i++){
        trie.insert(val[i],i);
    }
    sct.ma[0] = -1;
    sct.cma[0] = -1;
    int lastans = 0;
    cur = n;
    for(int i = 1;i<=m;i++){
        char c;
        cin>>c;
        if(c == 'I'){
            int x,y;
            cin>>x>>y;
            x = (x + lastans)%sct.uc[rot];
            y = (y + lastans)%1048576;
            x++;
            int now = ++cur;
            val[now] = y;
            sct.usf[now] = 1;
            sct.insert(rot,x,now,0,1,1e9);
            trie.insert(val[now],now);
        }else if(c == 'D'){
            int x;
            cin>>x;
            x = (x + lastans)%sct.uc[rot];
            x++;
            int p = sct.kth(rot,x);
            trie.remove(val[p],p);
            sct.remove(rot,x);
        }else if(c == 'C'){
            int x,y;
            cin>>x>>y;
            x = (x + lastans)%sct.uc[rot];
            y = (y + lastans)%1048576;
            x++;
            int p = sct.kth(rot,x);
            trie.remove(val[p],p);
            sct.remove(rot,x);
            int now = ++cur;
            val[now] = y;
            sct.usf[now] = 1;
            sct.insert(rot,x,now,0,1,1e9);
            trie.insert(val[now],now);
        }else{
            int l,r;
            cin>>l>>r;
            l = (l + lastans)%sct.uc[rot];
            r = (r + lastans)%sct.uc[rot];
            l++;
            r++;
            int lp = sct.kth(rot,l),rp = sct.kth(rot,r);
            pair<int,int> res = sct.qcma(rot,1,1e9,id[lp],id[rp]);
            lastans = trie.query(res.second,lp,rp);
            cout<<lastans<<'\n';
        }
    }
}